package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/03/05 11:17
 */
public class _189_轮转数组 {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int k = 3;


        int[] nums1 = {-1, -100, 3, 99};
        int k1 = 2;

        rotate3(nums1, k1);

        System.out.println(Arrays.toString(nums1));
    }

    /**
     * 方法一：使用List集合
     * 时间复杂度为O(n)
     * 空间复杂度为O(n)
     *
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;

        List<Integer> res = new ArrayList<>();
        for (int i = n - k; i < n; i++) {
            res.add(nums[i]);
        }
        for (int i = 0; i < n - k; i++) {
            res.add(nums[i]);
        }

        for (int i = 0; i < res.size(); i++) {
            nums[i] = res.get(i);
        }
    }

    /**
     * 方法二：换装替换
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param nums
     * @param k
     * @return
     * @author WangYX
     * @date 2024/03/05 14:13
     */
    public static void rotate1(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k, n);
        for (int start = 0; start < count; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
            } while (start != current);
        }

    }

    /**
     * 求最大公约数
     *
     * @param x
     * @param y
     * @return {@link int}
     * @author WangYX
     * @date 2024/03/05 14:14
     */
    public static int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    /**
     * 方法三：数组反转
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     *
     * @param nums
     * @param k
     * @return
     * @author WangYX
     * @date 2024/03/05 14:15
     */
    public static void rotate3(int[] nums, int k) {
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int num = nums[start];
            nums[start] = nums[end];
            nums[end] = num;
            start++;
            end--;
        }
    }


}
